package LeetCode._05_堆;

import java.util.*;

public class _692_前K个高频单词 {
    public List<String> topKFrequent(String[] words, int k) {
        if(words == null || words.length == 0) return new ArrayList<>();
        Map<String,Integer> map = new HashMap<>();
        for(String str : words){
            map.put(str,map.getOrDefault(str,0)+1);
        }
        //最小堆，存放每个单词，比较规则按照单词出现的次数，如果次数相同就按照字母顺序
        PriorityQueue<String> minHeap = new PriorityQueue<>((str1, str2)->{
          return map.get(str1).equals(map.get(str2)) ? str2.compareTo(str1) : map.get(str1) - map.get(str2);
        });

        for (String s : map.keySet()) {
            minHeap.offer(s);
            // 当堆中元素个数大于 k 个的时候，需要弹出堆顶最小的元素。
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }
        List<String> res = new ArrayList<>();
        while(!minHeap.isEmpty()){
            res.add(minHeap.poll());
        }
        Collections.reverse(res);
        return res;
    }
}
